/* 
 * File:   dijkstra.h
 * Author: kenji
 *
 * Created on December 19, 2013, 11:00 AM
 */

#ifndef DIJKSTRA_H
#define	DIJKSTRA_H

#include "graph.h"
#include <vector>
#include <queue>
#include <stdio.h>

#define INF 1<<30
#define GNode std::pair< int,int> 

class DijkstraAlgorithm
{
public:

    DijkstraAlgorithm(std::vector< GNode > * ady,int* vertexId, int size);

    ~DijkstraAlgorithm();

    std::vector<int> shortestPath(int beginId, int endId);

    std::vector<int> shortestPathExcludePoints(int beginId, int endId, std::vector<int> avoidPointsId);

    void print(int destino)
    {
        if (previous_[ destino ] != -1)
            print(previous_[ destino ]);
        printf("%d ", destino);
    };

private:

    void initArrays();

    void relax(int, int, int);

    int getPosById(int id);
    
    std::vector<int> getShortestPathIds(int endId);

    int size_;

    std::vector< GNode > * ady_; //the adjacency matrix

    int * distance_; // initialize by default 

    bool * visited_; // initialize by default

    int * previous_; // initialize by default

    int * vertexId_; //the id of all vertex

    std::priority_queue< GNode, std::vector<GNode>, std::greater<GNode> > queue_;

};



#endif	/* DIJKSTRA_H */

